<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2269：Locks and keys</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Locks and keys</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Locks and keys</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Locks and keys                </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p></p>
<p>A wizard is in a labyrinth where there are <span class="MATH"><i>V</i></span> rooms and <span class="MATH"><i>V</i> - 1</span> doors connecting some pairs of rooms in both directions, in such a way that there is always a sequence of doors one can traverse to go from a room to any other room. Additionally, there are <span class="MATH"><i>C</i></span> locks and <span class="MATH"><i>C</i></span> keys of <span class="MATH"><i>C</i></span> different colours (one of each) in some of the doors and rooms of the maze, respectively; each door has at most one lock, and there is at most one key placed in each room. It should be an easy matter for the wizard to bypass the lock system, were it not for the fact that he forgot his spell book, without which his wizardry is utterly useless. The wizard is currently in room <span class="MATH"><i>X</i></span>, and he wants to get his spell book, located in room <span class="MATH"><i>Y</i></span>, without taking too long. At every step he may go to an adjacent room through one of the doors. Of course, if the door is locked, he needs to be carrying the key of the same colour as the lock (unless, of course, that door has already been unlocked). The wizard can carry only one key at a time and after picking up a key it is not possible for him to drop it somewhere in the maze in order to take it again afterwards. Once a door has been unlocked, the key is thrown away since it is no longer any use.</p>
<p>Given the maze and the positions of the <span class="MATH"><i>C</i></span> keys and <span class="MATH"><i>C</i></span> locks, determine how to reach <span class="MATH"><i>Y</i></span> from <span class="MATH"><i>X</i></span>, if possible. Any path whose length does not exceed <!-- MATH
$4 \cdot (C + 1) \cdot V$
--><span class="MATH">4<sup> . </sup>(<i>C</i> + 1)<sup> . </sup><i>V</i></span> is acceptable.</p>
<p><span lang="EN-US"><font size="3"><font face="宋体">The first line of each case contains four integers: the number <span class="math"><i>V</i></span> of rooms in the maze (<!-- MATH
$1 \le V
\le 1\,500$
--> <span class="math">1&lt;=<i>V</i></span>&lt;=<span class="math">1&nbsp;500</span>), the number <span class="math"><i>C</i></span> of locks (<!-- MATH
$0 \le C < V$
--> <span class="math">0</span>&lt;=<span class="math"><i>C&lt;</i> <i>V</i></span>), and rooms <span class="math"><i>X</i></span> and <span class="math"><i>Y</i></span> numbered <span class="math"><!-- MATH
$0,1,\ldots,V-1$
-->0, 1,..., <i>V</i> - 1</span>. Then comes a (possibly empty) line with <span class="math"><i>C</i></span> integers indicating the location of each of the keys, in order of increasing colour. The next <span class="math"><i>V</i> - 1</span> lines describe the maze: each contains three integers <span class="math"><i>A</i>&nbsp;<i>B</i>&nbsp;<i>L</i></span>, meaning that there is a door between rooms <span class="math"><i>A</i></span> and <span class="math"><i>B</i></span> which can be unlocked with the key of colour <span class="math"><i>L</i></span>, if <span class="math"><!-- MATH
$0 \le L < C$
-->0</span>&lt;=<span class="math"><i>L</i> &lt; <i>C</i></span>; a value of <span class="math">-1</span> for <span class="math"><i>L</i></span> indicates that no lock is needed. <o:p></o:p></font></font></span></p>
<p><span lang="EN-US"><font size="3"><font face="宋体">The last line has <span class="math"><i><!-- MATH
$V, C, X, Y = 0, 0, 0, 0$
-->V</i>, <i>C</i>, <i>X</i>, <i>Y</i> = 0, 0, 0, 0</span>. <o:p></o:p></font></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US"><o:p><font face="Times New Roman" size="3">&nbsp;</font></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">一个巫师目前正被困在一个有着<span lang="EN-US">V</span>个房间和<span lang="EN-US">V-1</span>个连接着某些房间的门的迷宫里。当然，门都是可双向通行的，且总是可以从一个房间经过一系列的门到达另一个房间（就是一颗树嘛。。）。在某些房间里有钥匙，在某些门上有锁。锁和钥匙共有<span lang="EN-US">C</span>种颜色，每一种颜色都对应着唯一的钥匙和唯一的锁，一把钥匙可以开相同颜色的锁。一个门上最多有一把锁，一个房间里最多有一把钥匙。如果巫师没有丢失咒语书，锁对巫师形同虚设。现在，丢失了咒语书的巫师发不出任意一个巫术。巫师目前在<span lang="EN-US">X</span>号房间。他希望不花太多的时间就可以拿到他落在<span lang="EN-US">Y</span>房间的咒语书。他一步可以走到相邻的房间。当然喽，如果门上有锁，他还必须带上和锁同色的钥匙（如果锁被打开就没必要了）。巫师一次只能带一把钥匙，并且一旦拿起了一把钥匙，就不能把它随意地丢在迷宫里的某一个位置并在之后的某一时间捡起它。只有当钥匙开了门以后才能丢弃它。<span lang="EN-US"><o:p></o:p></span></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">给出迷宫的形态和<span lang="EN-US">C</span>个钥匙和<span lang="EN-US">C</span>个锁的位置。如果可以从<span lang="EN-US">X</span>到<span lang="EN-US">Y</span>，请给出方案。<b style="mso-bidi-font-weight: normal">任何一个不超过</b></font></span><b style="mso-bidi-font-weight: normal"><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMR10">4 </span></b><b style="mso-bidi-font-weight: normal"><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMSY10">*</span></b><b style="mso-bidi-font-weight: normal"><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMR10">(</span></b><b style="mso-bidi-font-weight: normal"><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMMI10">C </span></b><b style="mso-bidi-font-weight: normal"><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMR10">+ 1) </span></b><b style="mso-bidi-font-weight: normal"><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMSY10">* </span></b><b style="mso-bidi-font-weight: normal"><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMMI10">V</span></b><b style="mso-bidi-font-weight: normal"><span style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMMI10">步</span></b><font size="3"><b style="mso-bidi-font-weight: normal"><span style="font-family: 宋体">的方案都是可以被接受的（囧啊。。。。）</span></b><span style="font-family: 宋体">。<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p></p></p><hr/><h3>输入格式</h3><p><p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">包含多组测试数据。<span lang="EN-US"><o:p></o:p></span></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">每一个测试数据的第一行包含<span lang="EN-US">4</span>个整数：<span lang="EN-US">V</span>代表房间数（</font></span><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMR10">1</span><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMSY10">&lt;=</span><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMMI10">V</span><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMSY10">&lt;=</span><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMR10">1500</span><span style="font-family: 宋体"><font size="3">）<span lang="EN-US">,C</span>代表颜色数（<span lang="EN-US">0&lt;=C&lt;V</span>）和<span lang="EN-US">X</span>、<span lang="EN-US">Y</span>。房间被编号为<span lang="EN-US">0,1&hellip;V-1</span>。<span lang="EN-US"><o:p></o:p></span></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">接下来的一行包含了<span lang="EN-US">C</span>的整数表示<span lang="EN-US">C</span>把钥匙的位置，钥匙的颜色是递增的。<span lang="EN-US"><o:p></o:p></span></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">接下来的<span lang="EN-US">V-1</span>行描述了迷宫的形态：每一行包含了三个整数<span lang="EN-US">A</span>、<span lang="EN-US">B</span>、<span lang="EN-US">L</span>。表示在房间<span lang="EN-US">A</span>与<span lang="EN-US">B</span>间有一道双向门，门上挂着一把颜色为<span lang="EN-US">L</span>的锁；若<span lang="EN-US">L=-1</span>，表示门没锁。<span lang="EN-US"><o:p></o:p></span></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">最后一行为<span lang="EN-US">V,C,X,Y=0,0,0,0<o:p></o:p></span></font></span></p>
<p></p></p><hr/><h3>输出格式</h3><p><p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">每一个输入数据对应一行输出。<span lang="EN-US"><o:p></o:p></span></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-family: 宋体"><font size="3">如果没有解，输出</font></span><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMTT10">Impossible</span><span style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMTT10">。否则按<span lang="EN-US">L</span>：<span lang="EN-US">V0&hellip;VL</span>的格式输出。<span lang="EN-US">L</span>是总步数，应该有<span lang="EN-US">L&lt;=4(C+1)V</span>。<span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMTT10">X=V0,V1,&hellip;,VL-1,VL=Y</span><span style="font-size: 10pt; font-family: 宋体; mso-font-kerning: 0pt; mso-bidi-font-family: CMTT10">是一次经过的<span lang="EN-US">L+1</span>个点。任意两对数应该用一个空格分开，具体请参见样例。<span lang="EN-US"><o:p></o:p></span></span></p>
<p></p></p><hr/><h3>样例输入</h3><pre>1 0 0 0

3 1 0 2
1
0 1 -1
0 2 0

3 2 0 2
1 2
0 1 1
0 2 0

5 3 0 4
2 0 3
0 1 0
0 2 -1
1 3 1
2 4 2

0 0 0 0
</pre><hr/><h3>样例输出</h3><pre>0: 0
3: 0 1 0 2
Impossible
10: 0 2 0 1 0 1 3 1 0 2 4
</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>鸣谢李青林</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2269" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2269" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>